\chapter{Plan de contr\^ole} \label{chap:Plan de contr\^ole}

%\lhead[\fancyplain{}{}]%    
 % {\fancyplain{}{\bfseries }}%\setcounter{equation}{0}

%\section{Introduction}
\minitoc
\ochap{E}{n} tant que r\'eseau P2P, PosNet est un syst\`eme dynamique : l'espace des solutions et l'espace des pairs sont dynamiques. Des objets de recherche peuvent \`a tout 
moment \^etre ajout\'es ou retir\'es, affectant la topologie du graphe s\'emantique. De m\^eme, des pairs peuvent \`atout moment se joindre ou quitter le r\'eseau, affectant 
la distribution du graphe s\'emantique entre les pairs et par l\`a m\^eme le graphe des pairs.
Suivant l'analogie valable pour le plan de transfert des requ\^etes, on d\'esigne par \textbf{plan de contr\^ole} (\emph{control plane}) l'ensemble des op\'erations relatives \`a 
l'administration du r\'eseau \emph{overlay}. Ces op\'erations couvrent la construction et la maintenance tant du graphe s\'emantique que du graphe des pairs. \\
L'une des contraintes qui s'appliquent sur le plan de contr\^ole est la pr\'eservation de la continuit\'e du service de localisation : les op\'erations de contr\^ole ne doivent 
pas cr\'eer d'interruption dans le traitement des requ\^etes de recherche. On veut que le plan de contr\^ole soit transparent au plan de transfert des requ\^etes. \\
Consid\'erant PosNet comme un syst\`eme dynamique et concurrent, ce chapitre r\'epond \`a des questions telles que : Comment se distribue le graphe s\'emantique ? Comment se d\'ecouvrent 
les pairs ? Comment assurer la continuit\'e de service du plan de transfert des requ\^etes pendant les op\'erations de maintenance du r\'eseau \emph{overlay} ? 
Dans le but de faciliter la compr\'ehension des algorithmes de base du plan de contr\^ole, on commence par les d\'ecrire section xxx en se pla\c cant dans le cas s\'equentiel. 
Les aspects concurrents sont envisag\'es dans un deuxi\`eme temps, \`a la section xxx. 
%Enfin la derni\'ere section \'evoque la probl\'ematique de la tol\'erance aux pannes (cf. ???). 

\section{API du plan de contr\^ole\label{descriptionplandecontrole}}
Quatre types d'\'ev\'enements peuvent se produire dans un index, n\'ecessitant l'intervention du plan de contr\^ole : 
\begin{itemize}
	\item L'ajout ou la suppression d'un objet/\emph{handle}
	\item L'arriv\'ee ou le d\'epart d'un pair
\end{itemize}
On consid\`ere que chacune de ces modifications constitue une \og macro-proc\'edure \fg{} : leur compl\'etion requiert plusieurs \'etapes interm\'ediaires. Par exemple, 
la suppression d'un pair du r\'eseau entra\^ ine a minima la modification de chacun de ses (ex-)voisins. On diff\'erentiera dans la suite les \textbf{macro-modifications} 
(ou macro-proc\'edures) et les \textbf{micro-modifications} (ou \'etapes interm\'ediaires). Les micro-modifications sont des modifications \'el\'ementaires, des primitives 
de contr\^ole dont la port\'ee est locale au pair qui les ex\'ecute. Leur caract\`ere \og \'el\'ementaire \fg{} est l'assurance de leur efficacit\'e. \\
Les macro-modifications correspondant aux \'ev\'enement sus-cit\'es sont accessibles (dans l'ordre) via une \textbf{API client} :  
\begin{description}
\item{\emph{ajouterObjet} :} Prend en entr\'ee la description d'un objet et un \emph{handle}
\item{\emph{supprimerObjet} :} Prend en entr\'ee la description d'un objet et un \emph{handle}
\item{\emph{joindreReseau} } Prend en entr\'ee l'adresse IP de la machine cliente et un port
\item{\emph{quitterReseau} } Prend en entr\'ee l'adresse IP de la machine cliente et un port
\end{description}  
L'ex\'ecution de ces macro-modifications entra\^ ine l'ex\'ecution de micro-modifications accessibles via une \textbf{API de pair} : 
\begin{description}
\item{\emph{ajouterNoeud} :} Prend en entr\'ee la description d'un noeud
\item{\emph{supprimerNoeud} :} Prend en entr\'ee la description d'un noeud
\item{\emph{ajouterNoeudExt} :} Prend en entr\'ee la description d'un noeud, l'adresse et le port d'un pair
%\item{supprimerNoeudExt :} Prend en entr\'ee la description d'un noeud
\item{\emph{ajouterArc} :} Prend en entr\'ee la description d'un noeud source, la description d'un noeud destination, une \'etiquette
\item{\emph{supprimerArc} :} Prend en entr\'ee la description d'un noeud source, la description d'un noeud destination
%\item{ajouterArcExt :} Prend en entr\'ee la description d'un noeud source, la description d'un noeud destination, une \'etiquette
%\item{supprimerArcExt :} Prend en entr\'ee la description d'un noeud source, la description d'un noeud destination
\item{\emph{ajouterHandle} :} Prend en entr\'ee un \emph{handle} et la description d'un noeud
\item{\emph{supprimerHandle} :} Prend en entr\'ee un \emph{handle} et la description d'un noeud
\end{description}  
L'invocation sur le pair $p$ de l'op\'eration \emph{ajoutNoeud($n$)} signifie que $p$ se voit assigner la responsabilit\'e de $n$. Tandis que l'invocation de 
\emph{ajoutNoeudExt($n,a,q$)} signifie que $n$ a \'et\'e assign\'e \`a un pair $p'$ (distinct de $p$, d'adresse $a$ et de port $q$) mais que $n$ se trouve \^etre adjacent \`a 
(au moins) un noeud s\'emantique propre \`a $p$. Dans ce dernier cas, $p$ enregistre $p'$ en tant que responsable de $n$. Noter qu'un noeud peut \^etre enregistr\'e en tant 
que responsable pour de multiples noeuds s\'emantiques. \\
%\item[Suppression d'un noeud s\'emantique. ]{Pr\'e-condition : Un noeud s\'emantique est supprim\'e seulement une fois tous ses arcs entrants et sortants supprim\'es ;}
%\item[Ajout d'un lien s\'emantique. ]{Pr\'e-condition : L'ajout d'un lien s\'emantique implique la pr\'e-existence des deux noeuds s\'emantiques source et cible. Noter
% que l'un de ces noeuds peut appartenir \'e un autre pair ;}
%\item[Suppression d'un lien s\'emantique. ]{But : La suppression d'un lien s\'emantique intervient soit en cas de redondance, soit en cas de suppression du noeud source ou 
%du noeud cible.}
%\end{description}
Dans la suite de cette section, on se place exclusivement dans le \textbf{cas s\'equentiel} o\`u les macro-modifications s'ex\'ecutent et modifient le graphe de mani\`ere 
isol\'ee, \`a l'exclusion de toute autre macro-modification (note : les requ\^etes de recherche n'\'etant pas des modifications, elles sont autoris\'ees). Le cas s\'equentiel, 
simplifi\'e par-rapport au cas r\'eel concurrentiel, nous sert \`a des fins didactiques \`a pr\'esenter les algorithmes de base du plan de contr\^ole. Les pr\'eoccupations 
li\'ees \`a l'ex\'ecution concurrente des macro-modifications sont envisag\'ees ult\'erieurement, section \ref{sec:gestiondelaconcurrence}.
On commence par  %Cela comprend les traitements inter-pairs (protocole d'interaction entre pairs) et les traitements intra-pair (modifications locales \`a un pair). 
d\'efinir les conditions de validit\'e des op\'erations du plan de contr\^ole avant de d\'ecrire la cha\^ine de traitements d'une macro-modification dans PosNet.
Enfin on d\'ecrit pour chaque requ\^ete de contr\^ole l'algorithme associ\'e. %Cet algorithme doit v\'erifier les crit\'eres de validit\'e, de terminaison et de correction \'etablis. 

\subsection{Conditions de validit\'e du plan de contr\^ole }\label{sec:conditionsdevalidite}
%Afin d'assurer la validit\'e d'une s\'equence de modifications, il est donc n\'ecessaire d'ordonnancer celles-ci :
%\subsubsection{Crit\'eres de coh\'erence d'une macro-modification}
Chaque type de modification, est de nature \`a affecter la coh\'erence du syst\`eme, et donc \`a compromettre la localisation des solutions. Pour \^etre consid\'er\'ees \og 
valides \fg{}, les modifications dans PosNet doivent pr\'eserver la continuit\'e de service du plan de transfert des requ\^etes. Une requ\^ete de recherche ne peut \^etre 
bloqu\'ee le temps d'une modification d'un arc ou d'un noeud. Cela implique de pr\'eserver l'accessibilit\'e de toute solution dans l'index, quelques soient les 
transformations en cours dans le r\'eseau \emph{overlay} : il doit \^etre possible \`a tout moment de calculer un chemin sans vall\'ee, quelques soient le noeud source et 
le noeud destination et quelque soit l'\'etat du syst\`eme.     
La solution trouv\'ee pour PosNet est bas\'ee sur l'exploitation de la propri\'et\'e de \textbf{transitivit\'e} de la relation d'ordre. 
%Pour cela les algorithmes du plan de contr\^ole doivent respecter deux invariants :
%\begin{description}
%\item[La validit\'e du guidage dans le graphe s\'emantique :] Entre deux noeuds s\'emantique, les arcs doivent \'etre corrects : la relation d'ordre partiel doit \'etre 
%v\'erifi\'ee au sein de chaque sous-graphe du graphe s\'emantique. Cet invariant constitue la post-condition des requ\'etes d'ajout et de suppression d'un noeud s\'emantique. 
%Parmi les points \'e contr\'eler apr\'es un ajout : le nouveau noeud est il correctement reli\'e \'e ses plus petits majorants (ou parents) ? \'e ses plus grands minorants 
%(ses enfants) ? A l'inverse, parmi les points \'e contr\'eler apr\'es une suppression : les anciens parents du noeud supprim\'e sont ils bien reli\'es \'e leurs nouveaux 
%enfants ? Les anciens enfants du noeud supprim\'e sont ils bien reli\'es \'e leurs nouveaux parents ?
%\item[La validit\'e du routage dans l'overlay :] Entre deux pairs, les liens de routage doivent \'etre corrects : pour chaque paire de noeuds s\'emantiques adjacents 
%les informations doivent \'etre correctes \emph{des deux c\'et\'es}. En effet, un lien entre un noeud s\'emantique source $s_X$ appartenant au pair $X$ et un noeud 
%s\'emantique cible $s_Y$ appartenant au pair $Y$ est correct \emph{pour $X$} si et seulement si :
%\begin{itemize}
%\item $s_Y$ existe dans la partition du grape s\'emantique de $X$ ;
%\item un lien existe entre $s_X$ et $s_Y$ dans la partition de $X$ et qu'il porte l'\'etiquette correcte ;
%\item si $X$ sait que $s_Y$ appartient au pair $Y$.  
%\end{itemize}
%Cet invariant constitue la post-condition des requ\'etes d'entr\'ee et de d\'epart d'un pair.
%\end{description}
%Lorsque ces deux invariants sont v\'erifi\'es, le r\'eseau \emph{overlay} est dit \textbf{coh\'erent}. Une modification de PosNet est dite coh\'erente si elle conserve 
%la coh\'erence du syst\'eme. Un algorithme est dit \textbf{valide} s'il n'applique que des modifications coh\'erentes.\\ 
%\subsubsection{Absence d'interf\'erences avec le plan de transfert des requ\'etes} 
%Tout en respectant l'int\'egrit\'e et la coh\'erence du syst\'eme, un algorithme du plan de contr\'ele doit aussi maintenir la continuit\'e des services de localisation. 
%Une requ\'ete de recherche ne peut \'etre bloqu\'ee le temps d'une modification d'un arc ou d'un noeud. L'existence d'un chemin sans vall\'ee entre toute paire de noeuds 
%s\'emantiques dans le graphe doit \'etre maintenue, malgr\'e des modification simultan\'ees de ce graphe. 
%La solution trouv\'ee pour PosNet est bas\'ee sur l'exploitation de la propri\'et\'e de \textbf{transitivit\'e} de la relation d'ordre. 
On veut \`a tout moment conserver un chemin valide entre deux noeuds du graphe s\'emantique. Pour cela, PosNet est modifi\'e de mani\`ere conservatrice : l'ancien chemin n'est 
d\'efait qu'apr\`es la mise en place du nouveau. Cette au prix d'une moindre r\'eactivit\'e (allongement des routes). 
%Lors d'une requ\'ete d'ajout de noeud s\'emantique, ce n'est qu'une fois celui-ci ajout\'e et correctement reli\'e, que les anciens liens sont supprim\'es. Inversement, 
%lors d'une requ\'ete de suppression d'un noeud s\'emantique $n$, ce n'est qu'une fois les arcs des noeuds adjacents \'e $n$ mis-\'e-jour que les anciens arcs sortants et 
%entrants de $n$ sont supprim\'es. \\
[TODO : petit sch\'ema \`a 4 noeuds (x 2 ?)]\\
On introduit donc un \'etat transitoire du syst\`eme dans lequel co-existent simultan\'ement deux \'etats : l'ancien \'etat et ???. La coh\'erence de cet \'etat repose sur
 la validit\'e des liens transitifs : un graphe s\'emantique valide reste valide apr\`es ajout d'un arc transitif. En effet, les arcs transitifs n'entravent pas la correction
 des algorithmes de r\'esolution de requ\^etes, les chemins sans vall\'ee \'etant conserv\'es.
La pr\'eservation d'un chemin sans vall\'ee en exploitant la transitivit\'e de la relation d'ordre induit donc un ordre sur les micro-modifications : 
%On obtient le sch\'ema d'ordonnancement g\'en\'eral des micro-modifications :   : 
\begin{enumerate}
	\item D\'eclenchement des ajouts de noeuds s\'emantiques (dans un ordre quelconque) ;
	\item D\'eclenchement des ajouts d'arcs (dans un ordre quelconque) ;
	\item D\'eclenchement des suppressions d'arcs (dans un ordre quelconque ; avec \'eventuelle remise-\`a-jour des tables de routage \`a ) ; 
	\item D\'eclenchement des suppressions de noeuds s\'emantiques (dans un ordre quelconque) ;
\end{enumerate}  
La sous-section suivante d\'ecrit la mise-en-oeuvre de bout-en-bout d'une op\'eration de contr\^ole dans le respect du sch\'ema d'ordonnancement ci-dessus. 
[TODO preuve que le respect des contraintes de validit\'e assure aux macro la correction dans un graphe dyn amique]

\subsection{Traitement de bout-en-bout d'une macro-modification}
%Dans PosNet, un pair n'est responsable que d'un sous-graphe seulement du graphe s\'emantique. Or le champ d'action d'une macro-modification peut s'\'etendre sur les domaines 
%de plusieurs pairs. 
La sous-section pr\'ec\'edente d\'ecrit le sch\'ema d'ordonnancement \`a appliquer, pour chaque macro-modification, \`a l'ensemble des micro-modifications qui lui sont 
associ\'ees. Le calcul des micro-modifications et leur ordonnancement sont contr\^ol\'es dans PosNet de mani\`ere centralis\'ee, par un m\^eme pair. %La coordination des micro-
%modifications associ\'ees \'e une macro-modification est assur\'ee par le m\'eme pair, pendant toute la dur\'ee de la macro-modification. 
Le choix de ce pair \og coordinateur \fg{}, est arbitraire (en fonction du point d'entr\'ee de la requ\^ete de contr\^ole). Etant donn\'ee une macro-modification \`a ex\'ecuter, 
la t\^ache de coordination se d\'eroule donc en deux \'etapes cons\'ecutives : 
\begin{enumerate}
 \item \textbf{D\'ecision : }{Le pair coordinateur interroge le r\'eseau \emph{overlay} afin de d\'eterminer l'ensemble des mise-\`a-jour n\'ecessaires et les pairs impact\'es ;}
 \item \textbf{Orchestration : }{Le pair coordinateur d\'eclenche les mise-\`a-jour selon l'ordre d\'ecrit en \ref{sec:conditionsdevalidite}, en notifiant chaque pair 
impact\'e des micro-modifications lui incombant.}
\end{enumerate}
[??????????? TODO sch\'ema diagramme de transition : les 2 \'etapes de la synchronisation]\\
On insiste ici sur la g\'en\'ericit\'e de cette d\'ecomposition en deux \'etapes du plan de contr\^ole : elle vaut quelque soit la macro-modification \`a effectuer. Une version 
ult\'erieure de PosNet qui d\'efinirait une nouvelle fonctionnalit\'e de contr\^ole (ou macro-modification) l'ex\'ecuterait de la m\^eme fa\c con : une \'etape de d\'ecision 
d\'ecomposant la t\^ ache en modifications \'el\'ementaires n'ayant pas connaissance les unes des autres, suivie d'une \'etape de synchronisation mettant en oeuvre les 
modifications \'el\'ementaires selon un ordre assurant la coh\'erence globale du syst\`eme. \\
Durant l'\'etape de d\'ecision, les noeuds affect\'es par une macro-modification sont d\'etermin\'es en faisant appel \`a l'API de pair suivante : 
\begin{description}
\item[\textit{getParents($n$)} :]{Retourne l'ensemble $P(n)$ de tous les noeuds s\'emantiques plus petits majorants du noeud $n$.} %Ils constituent les futurs noeuds parents de $n$.}
\item[\textit{getEnfants($n$)} :]{Retourne l'ensemble $E(n)$ de tous les noeuds s\'emantiques plus grands minorants de $n$.} %Ils constituent les futurs enfants de $n$.}
\item[\textit{getNoyau} :]{Retourne $Noyau$, l'ensemble des noeuds s\'emantiques maximaux.}
\end{description}
A partir des ensembles de noeuds retourn\'es, le pair coordinateur est en mesure de d\'eduire l'ensemble des micro-modifications n\'ecessaires (sur les noeuds et sur les 
arcs) \`a la macro-modification en cours. \\
%\paragraph{Etape d'orchestration}
Durant l'\'etape d'orchestration d'une requ\^ete de contr\^ole, le pair coordinateur invoque dans l'ordre du sch\'ema d'ordonnancement les pairs concern\'es par une micro-modification. 
Pour un m\^eme type de micro-modification, l'ordre des pairs est quelconque. Une fois toutes les micro-modifications du m\^eme type accomplies, le pair coordinateur passe \`a 
la micro-modification suivante. Les r\`egles d'ordonnancement des micro-modifications \'etant les m\^emes quelques soient les macro-modifications, on observe que les 
macro-modifications se distinguent uniquement par les r\`egles de d\'ecision : quelle d\'ecomposition en micro-modifications pour chaque macro-modification ? 

Tout au long des \'etapes de d\'ecision et d'orchestration, les pairs communiquent par le biais d'un protocole de communication, lequel n'est pas directement accessible \`a 
l'utilisateur de l'index et permet depuis chaque pair de d\'eclencher une s\'equence de micro-modifications. \\
Ayant expos\'e la conception du plan de contr\^ole (API, crit\`eres de validit\'e, d\'eroulement d'une macro-modification), on a d\'esormais r\'eunis les pr\'e-requis n\'ecessaires 
\`a la compr\'ehension des algorithmes du plan de contr\^ole, qui font l'objet de la section suivante. 

\section{Description des algorithmes de d\'ecision}
Deux diff\'erents types de macro-modifications diff\'erent principalement par leur processus de d\'ecision, la synchronisation consistant \`a d\'eclencher les micro-modifications 
d\'ecid\'ees dans un ordre fixe, d\'ecrit ci-dessus. On se borne donc, pour chaque macro-modification, \`a d\'ecrire l'\'etape de d\'ecision. On commence par traiter le cas des 
macro-modifications associ\'ees \`a l'ajout et la suppression d'objet, avant de consid\'erer celles associ\'ees \`a l'entr\'ee et au d\'epart d'un pair.  

\subsection{Gestion des objets : ajout et suppression d'objets et de \emph{handle}}
Cette sous-section pr\'esente une description litt\'erale de l'algorithme de d\'ecision, suivi de son pseudo-code et d'exemples. On raisonne sur le graphe s\'emantique $G(S,A)$ 
avant modifications, avec $S$ l'ensemble des sommets d'origine et $A$ l'ensemble des arcs d'origine.\\

\subsubsection{Description de l'algorithme} Le pair coordinateur commence par d\'eterminer si la macro-modification occasionne ou non une modification du graphe s\'emantique. 
Selon la nature de la macro-modification, le pair peut se trouver dans les cas suivants : 
\begin{itemize}
	\item Il s'agit de rajouter un \emph{handle} \`a un objet d\'ej\'a index\'e ;
	\item Il s'agit de supprimer un \emph{handle} \`a un objet d\'ej\`a index\'e ; 
	\item Il s'agit de rajouter un nouvel objet (non d\'ej\`a index\'e) ;
	\item Il s'agit de supprimer un objet index\'e. 
\end{itemize}
Dans les deux premiers cas, la macro-modification demand\'ee ne modifie pas $S$ : la topologie d'origine de $G$ reste inchang\'ee. La macro-modification \emph{ajoutNoeud} 
(respectivement \emph{supprimeNoeud}) se r\'eduit \`a l'enregistrement (resp. \`a la suppression) de $h$ associ\'e \`a $n$ aupr\`es du pair propri\'etaire de $n$. Si le dernier 
\emph{handle} est supprim\'e, le noeud est malgr\'e tout conserv\'e dans le graphe, pour servir au guidage. \\
A contrario, dans les deux derniers cas, $S$ doit \^etre modifi\'e par ajout ou suppression de noeud, selon. Le graphe s\'emantique \'etant connexe, une modification de $S$ 
entra\^ine des modifications dans $A$. L'ajout et la suppression \'etant deux probl\`emes inverses, on d\'etaille dans ce qui suit uniquement l'algorithme correspondant \`a 
l'ajout d'un objet. La suppression peut \^etre directement d\'eduite de l'ajout en inversant les \'etapes.
Le calcul de ces modifications d'arcs (ajout et suppression) est entrepris lors de l'\'etape de d\'ecision selon les modalit\'es suivantes (les num\'eros de ligne renvoient 
au pseudo-code plus bas) : 
\begin{itemize}
	\item Sont calcul\'es l'ensemble des \og futurs \fg{} noeuds enfants $E(n)$ (ligne 1) et l'ensemble des \og futurs \fg{} noeuds parents $P(n)$ du noeud \`a ajouter 
$n$ (ligne 2) ; 
	\item Sont d\'esign\'es comme \og \`a ajouter \fg() les nouveaux arcs entre $n$ et ses enfants, aussi bien de type \og c2p \fg que \og p2c \fg (ligne 11) ; idem pour 
$n$ et ses parents (ligne 13) ;
	\item S  ont d\'esign\'es comme \og \'e supprimer \fg les arcs transitifs qui seraient cr\'ees (ligne 10) ;
  	\item Est g\'er\'e le cas o\`u $n$ est un nouveau noeud maximal. Dans ce cas $n$ v\'erifie les conditions suivantes : $|P(n)|=0$ (ligne 12), l'ensemble des noeuds-co-maximaux 
(non repr\'esent\'e ici) est non nul et $E(n)$ est compos\'e de 0 ou plus noeuds maximaux de la topologie d'origine. En cons\'equence, sont marqu\'es \og \`a ajouter \fg 
les liens de type \og m2m \fg entre $n$ et chacun des \'el\'ements maximaux d'origine (ligne 16), \`a l'exception de ceux qui font partie de ses enfants (ligne 6). Ceux-ci 
doivent \^etre reli\'es \`a $n$ par des des arcs de type \og c2p \fg et \og p2c \fg : ces arcs sont donc d\'esign\'es comme \og \`a ajouter \fg() (ligne 8). 
\end{itemize}

\subsubsection{Pseudo-code de l'\'etape de d\'ecision}[]

\begin{tabular}{l}
\hline
$E_{n} \, := \, getEnfants(n)$ \, // \, \textit{l'ensemble des noeuds enfants de $n$ calcul\'e sur $S\cup\{n\}$}\\
$P_{n} \, := \, getParents(n)$ \, // \, \textit{l'ensemble des noeuds parents de $n$ calcul\'e sur $S\cup\{n\}$}\\
$Noyau \, := \, getNoyau()$ \, \\
$S_{a} \, := \, \varnothing$ \, // \, \textit{les liens \`a ajouter}\\
$S_{r} \, \, := \, \varnothing$ \, // \, \textit{les liens \`a supprimer}\\
\textbf{for each} $e$ in $E(n)$\textbf{:}\\
\phantom{x}\textbf{if} $e \in Noyau$ \textbf{then:} \\
\phantom{x}\phantom{x}\textbf{for each} $t$ in $Noyau$\textbf{:} \textbf{add} $e \xrightarrow{\sim} t$ and $t \xrightarrow{\sim} e$ to $S_{r}$\\
\phantom{x}$P(e) \, := \, getParents(e)$ \, // \, \textit{getParents(e) est calcul\'e sur $S\cup\{n\}$}\\
\phantom{x}\textbf{for each} $p_e$ in  $P(e)$, \\
\phantom{x}\phantom{x}\textbf{if} $p_e \in P(n)$ \textbf{then:} \textbf{add} $e \xrightarrow{<} p_e$ and $p_e \xrightarrow{>} e$ to $S_{r}$\\
\phantom{x}\textbf{add} $e \xrightarrow{<} n$ and $n \xrightarrow{>} e$ to $S_{a}$\\ 
\textbf{if} $\vert P(n) \vert$ > 0 \textbf{then:} \\
\phantom{x} \textbf{for each} $p$ in $P(n)$\textbf{:} \textbf{add} $n \xrightarrow{<} p$ and $p \xrightarrow{>} n$ to $S_{a}$ \\
\textbf{else:}\\
\phantom{x}\textbf{for each} $t$ in $Noyau$\textbf{:} \\
\phantom{x}\phantom{x}\textbf{if} $t \notin E(n)$  \textbf{then:} \textbf{add} $n \xrightarrow{\sim} t$ and $t \xrightarrow{\sim} n$ to $S_{a}$\\
 %\textbf{choose} $N_r \in R$ // \textit{the overlay node responsible for }$n$\\
%\textbf{send} a control message to $N_r$ to add the node $n$\\
%\textbf{for each} overlay node $N$ in $R$\textbf{:} \\
%\phantom{x}\textbf{send} control message to $N'$ to add links from $S_{a}$ \\
%\phantom{x}\textbf{send} control message to $N'$ to remove links from $S_{r}$ \\
\hline
\end{tabular}

\subsubsection{Exemples}
Par souci de clart\'e, on traite en deux exemples : le cas o\`u le nouveau noeud doit \^etre ins\'er\'e dans le noyau et le cas o\`u l'insertion du nouveau noeud entra\^ine 
l'apparition d'arcs transitifs. 
\paragraph{Exemple 1 : Cas o\`u le nouveau noeud doit \^etre ins\'er\'e dans le noyau}
On reprend notre topologie de graphe s\'emantique de r\'ef\'erence. Que donne l'ex\'ecution de la macro-modification \emph{ajouter\_objet((10,2))} ($n=(10,2)$) ?\\
L'\'etape de d\'ecision commence par calculer $E(n) = \left\{ (10,1),(4,2) \right\}, \, P(n)=\{\},Noyau=\{(8,10),(9,9),(10,1)\}$ : on est dans le cas o\`u le nouveau noeud
 $n$ est maximal par-rapport \`a l'ensemble de noeuds d'origine. 
Puisque $(10,1)$ est domin\'e par $(10,2)$, il cesse d'appartenir au noyau est doit donc \og en \^etre d\'etach\'e \fg. On marque donc \og \`a supprimer \fg (c'est-\`a-dire que 
l'on ajoute dans $S_r$) les arcs $(10,1) \xrightarrow{\sim} (8,10)$, $(10,1) \xleftarrow{\sim} (8,10)$, $(10,1) \xrightarrow{\sim} (9,9)$ et $(10,1) \xleftarrow{\sim} (9,9)$ (ligne 7). 
On ajoute dans $S_a$ la relation entre $(10,1)$ et $(10,2)$ avec les arcs $(10,1) \xrightarrow{<} (10,2)$ et $(10,2) \xrightarrow{>} (10,1)$. De m\^eme, on ajoute dans $S_a$ 
la relation entre $(4,2)$ et $(10,2)$ avec les arcs $(4,2) \xrightarrow{<} (10,2)$ et $(10,2) \xrightarrow{>} (4,2)$. 
Enfin, puisque $(10,2)$ appartient d\'esormais au noyau il faut le relier aux noeuds maximaux restants. On ajoute donc dans $S_a$ les arcs $(10,2) \xrightarrow{\sim} (8,10)$, 
$(10,2) \xleftarrow{\sim} (8,10)$, $(10,2) \xrightarrow{\sim} (9,9)$ et $(10,2) \xleftarrow{\sim} (9,9)$ (ligne 16). 
Finalement, on obtient : $S_a=\{(10,1) \xrightarrow{<} (10,2),(10,2) \xrightarrow{>} (10,1),(4,2) \xrightarrow{<} (10,2),(10,2) \xrightarrow{>} (4,2),(10,2) \xrightarrow{\sim} 
(8,10),(10,2) \xleftarrow{\sim} (8,10),(10,2) \xrightarrow{\sim} (9,9),(10,2) \xleftarrow{\sim} (9,9)\}$ 
et $S_r=\{(10,1) \xrightarrow{\sim} (8,10),(10,1) \xleftarrow{\sim} (8,10),(10,1) \xrightarrow{\sim} (9,9),(10,1) \xleftarrow{\sim} (9,9)\}$. \\
Lors de l'\'etape de synchronisation, les micro-modifications correspondant \`a l'\'etape de d\'ecision sont d\'eclench\'ees par lot dans l'ordre suivant 
(l'ordre au sein d'un lot est arbitraire) : 
\begin{enumerate}
	\item Ajout du noeud (10,2) dans un pair ;
	\item Ajout des arcs appartenant \`a $S_a$ ;
	\item Suppression des arcs appartenant \`a $S_r$.
\end{enumerate}
%L'affectation d'un noeud s\'emantique se fait en fonction de la localisation de ses voisins (parents ou enfants) ??
L'\'etape d'ajout du noeud dans un pair n'est pas d\'etaill\'ee ici. Le choix du pair rel\'eve d'une probl\'ematique distincte, trait\'ee en ???. Pour le moment, 
et pour simplifier les choses, on admet que ce choix se fait de mani\'ere arbitraire. 
[TODO : Sch\'ema avec d'un c\'et\'e le GS d'origine, de l'autre le GD modifi\'e apr\'es insertion de n. mettre en \'evidence les arcs modifi\'e (ajout\'es ET supprim\'es)]
\paragraph{Exemple 2 : Cas o\`u l'insertion du nouveau noeud entra\'ene l'apparition d'arcs transitifs}
Toujours sur la topologie de graphe s\'emantique de r\'ef\'erence, on ex\'ecute la macro-modification \emph{ajouter\_objet((7,9))} ($n=(7,9)$) :\\
On a ici $E(n) = \left\{(4,2) \right\}, \, P(n)=\{ (7,3) \},Noyau=\{(8,10),(9,9),(10,1)\}$. Dans la suite, $e=(4,2),P(e)=(7,3)$. La valeur du test \textbf{if} $p_e \in P(n)$ 
est donc vrai : un parent d'un enfant de $n$ est lui m\^eme parent de $n$. Les arcs reliant $(4,2)$ et $(7,3)$, apr\`es modification du graphe, deviendraient transitifs : il est 
n\'ecessaire de les supprimer. On ajoute donc \`a $S_r$ les arcs $(7,3) \xrightarrow{>} (4,2)$ et $(7,3) \xleftarrow{<} (4,2)\}$. A l'issue de la proc\'edure de d\'ecision, on 
obtient : $S_a=\{(7,2) \xrightarrow{<} (7,3),(7,2) \xleftarrow{<} (7,3),(4,2) \xrightarrow{<} (7,2),(4,2) \xleftarrow{<} (7,2)\}$ 
et $S_r=\{(7,3) \xrightarrow{>} (4,2),(7,3) \xleftarrow{>} (4,2)\}\}$. \\
>>>>>>>>>TODO : Sch\'ema avec d'un ct\'e le GS d'origine, de l'autre le GD modifi\'e apr\'es insertion de n. mettre en \'evidence les arcs modifi\'e
\subsection{Gestion des pairs : entr\'ee et sortie d'un pair}
%Le caract\'ere semi-structur\'e de PosNet offre l'avantage de pouvoir contr\^oler le placement des donn\'ees et la topologie des pairs, et donc d'en tirer avantage. 
%La section suivante d\'etaille quels avantages et de quelle mani\'ere.\\
\subsubsection{Probl\'ematique}
% ********ETAT DE L ART SUR LES SYSTEMES LOOSELY STRUTURED http://www.iwayan.info/Research/Understanding/ThesisBourogne/Thesis_IWayan_Final/MainThesisIWS/node36.html
% ********Inclure 3Sons et Symphony (bas\'es Chord)/Freenet/ 
% --- POSNET, UN SYSTEME DYNAMIQUE
Dans un syst\`eme distribu\'e dynamique, des pairs peuvent \`a tout instant se joindre ou quitter le syst\`eme\footnote{Les serveurs ne participant pas au r\'eseau logique ne sont 
pas consid\'er\'es ici. En effet, leur arriv\'ee ou leur d\'epart du syst\`eme peut entra\'ener une mise-\`a-jour des \emph{handlers} ou des objets index\'es, mais n'entra\^ine pas de 
re-distribution du graphe s\'emantique.}. 
% --- ENTREE/SORTIE DES PAIRS => RE DISTRIBUTION DES NOEUDS SEMANTIQUES => MODIFICATION DU GRAPHE DES PAIRS
%L'entr\'ee ou la sortie d'un pair dans PosNet se traduit par une re-distribution des noeuds s\'emantiques entre pairs :
L'entr\'ee ou la sortie d'un pair se traduit par un partitionnement de l'espace des solutions. 

\begin{itemize}
	\item Lorsqu'un pair se joint \`a l'overlay, une partition du graphe s\'emantique doit lui \^etre attribu\'e. 
Un ou plusieurs pairs d\'ej\`a connect\'es au r\'eseau vont lui d\'el\'eguer un sous-ensemble de leurs noeuds s\'emantiques ; 
	\item Lorsqu'un pair quitte l'overlay, la supervision de la partition dont il avait la charge doit \^etre transf\'er\'ee. 
Le pair sortant va d\'el\'eguer ses noeuds s\'emantiques \`a un ou plusieurs pairs demeurant dans l'overlay.  
\end{itemize}

[TODO 2 Sch\'emas en face \`a face : un pair arrive et un autre partage sa partition avec lui/un pair s en va et d\'el\'egue sa partition \`a un autre]\\
Selon la d\'efinition d'un \'etat du syst\`ame, caract\'eris\'e dans le chapitre xxx par l'application $M:N->K$ %terminaison SWAM
, l'entr\'ee ou la sortie d'un pair modifie donc l'\'etat de notre syst\`eme. 
Lors de ce changement d'\'etat, deux propri\'et\'es doivent\^etre v\'erifi\'ees : 
\begin{enumerate}
	\item La correction des proc\'edures d'entr\'ee et de d\'epart d'un pair 
	\item La continuit\'e de service 
\end{enumerate}
%\'etat = distribution du graphe s\'emantique = l'ensemble des pairs et pour chaque pair, les objets qu'il g\`ere (et qui d\'eterminent son voisinage) [TODO : formaliser la notion 
%d'\'etat ? formaliser dans le chapitre 4 ?].
Durant un changement d'\'etat du syst\`eme, la question se pose de sa disponibilit\'e. En d'autres termes : est-il possible de maintenir la continuit\'e du service de recherche 
pendant une modification du syst\`eme ? En effet, comme vu au chapitre xxx, la validit\'e de l'\'etat de l'\emph{overlay} est une condition n\'ecessaire de la propri\'et\'e de terminaison 
des algorithmes de recherche. On rappelle que pour qu'un \'etat soit valide, il faut :
\begin{itemize}
	\item Pour chaque pair : un graphe s\'emantique valide 
	\item Pour l'ensemble des pairs : un graphe des pairs valide
\end{itemize}
Ainsi, en cas d'erreurs dans les tables de routage des pairs un noeud s\'emantique peut devenir inaccessible, affectant le taux de \emph{recall} du service. La disponibilit\'e du 
service de recherche est donc un enjeu des  
On impose donc que la continuit\'e du service de recherche soit une propri\'et\'e de vivacit\'e%\footnote{Dans notre cas, on consid\`ere que les propri\'et\'es de s\'ecurit\'es couvrent la 
%classe des propri\'et\'es d\'ecrivant un ensemble de bons \'etats qui restent invariants.} 
des proc\'edures de gestion des entr\'ees/sorties des pairs. \\

\subsubsection{Propri\'et\'e de s\'eret\'e} 
La continuit\'e du service de recherche % Qu'entend on par continuit\'e de service ? 
La propri\'et\'e de s\'eret\'e devant \^etre v\'erifi\'ee par les proc\'edures de gestion des pairs peut \^etre formul\'ee comme : toute requ\^ete est satisfaite en un temps born\'e. %si pas mention 
%de temps born\'e, alors propri\'et\'e de vivacit\'e ??

Le premier objectif, lors de la gestion de la dynamicit\'e de l'ensemble des pairs $P$, est de pr\'eserver la connexit\'e du graphe des pairs : soit deux noeuds s\'emantiques 
$n_s$ et $n_d$, il doit y avoir au moins un chemin reliant $n_s$ \`a $n_d$ avant et apr\`es toute modification de $P$. On sait que le graphe s\'emantique poss\`ede la propri\'et\'e 
d'\^etre connexe. On se propose donc d'assurer la connexit\'e du graphe des pairs en posant deux invariants. Ces invariants doivent \^etre v\'erifi\'es avant et apr\`es chaque 
modification et sont les suivants :  
\begin{enumerate}
	\item Le graphe s\'emantique doit \^etre correct 
\end{enumerate}

Lorsque ces conditions sont satisfaites, le graphe des pairs est dit \textbf{coh\'erent}.

\subsubsection{Propri\'et\'e de vivacit\'e}

Le graphe des pairs d\'ependant de la distribution du graphe s\'emantique, la modification de cette distribution peut avoir une incidence sur les chemins emprunt\'es dans le 
r\'eseau \emph{overlay}. \\ 
>>>>>>>>>TODO Sch\'ema : pour un chemin entre deux points sur deux pairs, montrer un nouveau chemin cr\'ee par l'ajout d'un 3\`eme pair\\

La seconde propri\'et\'e est une propri\'et\'e de vivacit\'e, qui exprime que m\^eme s'il n'est pas possible d'optimiser globalement les performances de recherche, il est possible de les optimiser 

% AVANT DE PARLER D OPTIMISATION D UN ETAT, PARLER DE SA CORRECTION
On \'evalue un \'etat de PosNet selon deux crit\`eres. Le premier crit\`ere \'evalue le co\^ut des recherches dans le syst\`eme et le second le co\^ut de la maintenance du syst\`eme :
%Admettons les crit\`eres d'\'evaluation d'une politique de re-distribution de graphe s\'emantique suivants : 
%\begin{itemize}
%	\item La longueur moyenne des routes : La longueur d'une route est calcul\'ee en nombre de pairs visit\'es. La longueur moyenne des routes est calcul\'ee en faisant 
%varier al\'eatoirement le pair d'entr\'ee et la valeur des attributs et en fixant les variables suivantes : 
%\begin{itemize}
%	\item Un \'etat de l'\emph{overlay} (caract\'eris\'e par un nombre de pairs $N$, une nombre d'objets stock\'es $k$),
%	\item Une dimension $d$, 
%	\item Une distribution des objets (parmi uniforme, normale, non-normale, Zipf ???\) 
%	\item Les dimensions
%\end{itemize}
%	\item La taille moyenne des tables de routage. La taille d'une table est caract\'eris\'ee par le nombre de pairs adjacents, chaque voisin \'etant multipli\'e par le nombre 
%de noeuds s\'emantiques adjacent par voisins
%\end{itemize}
\begin{enumerate} %EN GROS - d\'etailler dans chapitre Evaluation
	\item La longueur moyenne des routes dans cet \'etat. La longueur d'une route est calcul\'ee pour une requ\^ete donn\'ee comme la somme totale des sauts successifs 
(\emph(hop count)) entre un pair source et chaque pair destination ; 
	\item La taille moyenne des tables de routage dans cet \'etat. La taille d'une table de routage est calcul\'ee en nombre d'entr\'ees dans cette table, chaque entr\'ee 
correspondant \`a la clef d'un noeud s\'emantique maintenu par un pair voisin (et la valeur \'etant le \emph{handler} de celui-ci).   
\end{enumerate}

La gestion de la dynamicit\'e des pairs consiste donc \`a trouver une politique de re-partitionnement qui optimise ces deux crit\`eres. On veut en effet que 

Une politique optimale de re-partitionnement du graphe s\'emantique pourrait se formuler comme un probl\`eme d'optimisation combinatoire dont la fonction objectif prendrait 
en compte \`a la fois : 
La satisfaction de cette fonction objectif n\'ecessite la connaissance de ???. 

[TODO : d\'emontrer une garantie probabiliste : l'heuristique fournit souvent, mais pas toujours, de bonnes solutions]

Or cette information est de nature globale et par cons\'equent, non disponible pour les pairs de PosNet. Dans notre syst\`eme, la re-distribution du graphe s\'emantique ne peut 
reposer que sur des d\'ecisions locales : un pair partage ses noeuds s\'emantiques, ou au contraire absorbe des noeuds s\'emantiques, sans avoir la connaissance du reste du graphe 
s\'emantique. On en conclut que dans PosNet, il n'est pas possible de garantir des propri\'et\'es globales au  sch\'ema de distribution du graphe s\'emantique, et partant, au routage 
des requ\^etes dans PosNet. On ne cherche pas \`a atteindre une topologie optimale du graphe s\'emantique dans sa globalit\'e, puisqu'on a vu qu'elle n'\'etait pas accessible par le 
biais de d\'ecisions uniquement locales. On veut un algorithme de bi-partitionnement ad hoc, qui soit meilleur qu'un bi-partitionnement al\'eatoire, tout en restant le plus 
simple possible. Le r\'esultat obtenu peut ensuite \'eventuellement servir de substrat \`a des algorithmes de raffinement comme on le verra \`a la section suivante (\ref{optimisation}).

\subsubsection{Description de l'algorithme}
On d\'ecrit dans ce qui suit le protocole d'entr\'ee d'un pair dans le syst\`eme. Le protocole de d\'epart peut \^etre directement d\'eduit de l'arriv\'ee en inversant les \'etapes. \\
Pour qu'un pair puisse se joindre au r\'eseau, il faut qu'un pair appartenant au r\'eseau partage avec lui sa partition du graphe s\'emantique. Ce processus d'int\'egration d'un 
pair n\'ecessite trois \'etapes : 
\begin{description}
\item \textbf{Etape de recherche} : Le pair entrant $p_e$ commence par r echercher parmi les pairs appartenant au r\'eseau un pair qui va lui d\'el\'eguer une partie de ses 
noeuds s\'emantiques (ce pair est d\'esign\'e dans la suite comme le \og pair candidat \fg{}). Le protocole impl\'ement\'e de recherche d'un pair candidat est tr\'es simple : $p_e$ 
interroge le r\'eseau pair apr\`es pair jusqu'\`a ce que l'un d'eux accepte de partager ses noeuds s\'emantiques. Le protocole est amorc\'e par le syst\`eme, qui d\'esigne \`a $p_e$ le 
premier pair \`a interroger. Ce pair, choisi arbitrairement, constitue le point d'entr\'ee de $p_e$ dans le syst\`eme. En cas de refus de la part d'un pair interrog\'e, celui-ci 
informe $p_e$ des identifiants de ses voisins et l'\'etape de n\'egociation se poursuit entre $p_e$ et les voisins. Cette \'etape se poursuit jusqu'\`a \'epuisement des pairs du 
r\'eseau (signant l'\'echec du processus d'int\'egration du pair). Actuellement, le refus est motiv\'e par [TODO compl\'eter]. En cas d'acceptation d'un pair,la deuxi\`eme \'etape du 
processus d'int\'egration est enclench\'ee ;
\item \textbf{Etape de bi-partitionnement} : Une fois un pair candidat d\'esign\'e, celui-ci doit d\'ecomposer en deux (bi-partitionner) sa partition du graphe s\'emantique et 
affecter une des sous-partitions ainsi obtenues \`a $p_e$. Intuitivement, l'approche adopt\'ee est de scinder la partition d'origine $p_o$ dans \fg le sens de la longueur \og{}, 
en \fg d\'etachant des grapes de noeuds \og{} \`a partir des noeuds maximaux. Le pseudo-code relatif au bi-partitionnement est d\'ecrit \`a la sous-section 
\ref{pseudocodebipartitionnement}. Son fonctionnement est le suivant (les num\'eros de ligne renvoient au pseudo-code donn\'e en-dessous). 
%\begin{itemize}
%	\item On assigne un noeud maximal sur deux au pair candidat, les autres au pair entrant ; 
%	\item 
L'algorithme utilise un parcours de type en largeur d'abord de $p_o$. Le parcours d\'ebute \`a un noeud maximal et est appel\'e r\'ecursivement sur l'ensemble des noeuds enfants. 
Lorsque tous les noeuds feuille accessibles \`a partir d'un noeux maximal ont \'et\'e visit\'es, le parcours reprend \`a un autre noeud maximal (jusqu'\`a \'epuisement des noeuds maximaux). 
Dans le cas o\`u le pair candidat poss\`ede un sommet maximal unique, on se ram\`ene au cas nominal (au moins deux noeuds maximaux) en scindant $p_o$ au niveau de la premi\`ere branche 
(on n'autorise pas le re-partitionnement dans le cas d'une partition d'origine restreinte \`a une cha\^ine unique). Chaque noeud travers\'e est marqu\'e ; ce marquage va ensuite d\'ecider 
de son affectation \`a l'un des deux pairs. Les noeuds maximaux sont alternativement marqu\'es comme appartenant au pair candidat ou au pair entrant [AH OUI ???]. Chaque noeud 
accessible \`a partir d'un noeud maximal donn\'e est marqu\'e comme ce noeud maximal. 
L'algorithme autorise le marquage multiple : un m\^eme noeud pouvant \^etre travers\'e plusieurs fois, il peut \^etre potentiellement marqu\'e comme appartenant aux deux pairs \`a la fois. 
Pour d\'epartager les pairs, un choix est fait, arbitraire : on attribue un noeud pouvant appartenir aux deux pairs au m\^eme pair \`a chaque fois, le pair candidat [TODO discuter de 
l'opportunit\'e de d\'enombrer le nombre de tags d\'epos\'es par flot => la couleur dominante l'emporte]. L'absence de boucle est garantie [TODO compl\'eter].\\
On note que cet algorithme \fg favorise \og{} le noeud candidat, qui conserve dans sa partition des cha\^ines compl\`etes, et \fg d\'efavorise \og{} le pair entrant, qui re\`eoit une 
partition moins connexe que celle du pair candidat. 
%\end{description}
\item \textbf{Etape de finalisation} : Une fois marqu\'es les noeuds s\'emantiques du noeud candidat, restent \`a effectuer \fg r\'eellement \og{} le bi-partitionnement
effectuer les micro-modifications n\'ecessaires \`a la finalisation de la macro-modification d'ajout de pair. Ces micro-modifications sont effectu\'ees selon l'ordre d\'ecrit en ??? : 
\begin{itemize}
	\item Le pair entrant doit \fg assimiler \og{} les noeuds s\'emantiques qui lui ont \'et\'e attribu\'es. L'attribution est op\'er\'ee par le noeud candidat, en d\'eclenchant sur le 
pair entrant une s\'equence de micro-modifications de type \fg ajouter noeud s\'emantique \og{} ;
	\item Les pairs candidat et entrant doivent remettre-\`e-jour leur voisinage. 
\end{itemize}

Protocole de mise-\`e-jour des tables de routage du pair entrant et des ses voisins ;
\end{description}
[TODO sch\'ema]

\subsubsection{Pseudo-code de l'algorithme de bi-partitionnement}\label{pseudocodebipartitionnement}
%La corr\'elation entre ces deux op\'erations et la probl\'ematique de r\'epartition de charge est trait\'ee au chapitre \og Perspectives \fg{} {[}corr\'elation entre ces 2 objectifs : 
%les noeuds \`a forte centralit\'e ?]. 
%Le reste de la sous-section traite des autres d\'eterminants des politiques d'entr\'ee et de d\'epart d'un pair. en s'axant sur l'entr\'ee (d\'epart : probl\'ematique du choix du pair 
%restant \`a qui d\'el\'eguer le GS du pair partant -> A TRAITER).

\subsubsection{Exemple}

\subsubsection{Optimisation : utilisation d'un protocole de stabilisation}\label{optimisation}

L'algorithme de re-partitionnement pr\'esent\'e ci-dessus repose uniquement sur des d\'ecisions locales, prises par les pairs individuellement sans concertation avec les autres pairs. 
La cons\'equence en est qu'il n'est pas possible de garantir des propri\'et\'es sur le sch\'ema de distribution du graphe s\'emantique sur les pairs. 

 
Pour la gestion de syst\`emes dynamiques, Shlomi Dolev et Ted Herman dans [Superstabilizing Protocols for Dynamic Distributed Systems] citent de nombreux travaux \`a l'appui d'une 
approche fond\'ee sur les protocoles d'auto-stabilisation. Selon cette approche, un syst\`eme auto-stabilisant se trouve dans un \'etat dit incoh\'erent suite \`a une changement de 
configuration. Partant de cet \'etat incoh\'erent, le syst\`eme va converger vers un \'etat dit coh\'erent, en fonction de la nouvelle configuration. Autrement dit, un syst\`eme ou un 
algorithme r\'eparti est un dit auto-stabilisant s'il v\'erifie sa sp\'ecification apr\`es un temps de stabilisation quelque soit sa configuration initiale. On en d\'eduit que la 
propri\'et\'e d'auto-stabilisation est appropri\'ee pour la conception d'un r\'eseau \emph{overlay} par la tol\'erance aux perturbations transitoires du syst\`eme.

L'approche est relativement simple : on alterne les phases de bi-partitionnement et de raffinement, une partition raffin\'ee servant de solution initiale aux partitionnements 
suivants.


We claim that self-stabilization is appropriate for the purpose of
building an overlay network because it allows the system to recover from any
perturbation affecting either a link or a local variable. It then verifies its specification
until the next failure.\\
In this section we prove that the code of ??? is a self-stabilizing implementation of a PosNet overlay building algorithm in a dynamic network environement. That is, if at 
some time $t_0$ faults and topological changes cease, then eventually the routing tables define a valid overlay at each peer and . NON!!!!!!!!!!!!!!!!!

%Le probl\`eme standard du partitionnement de graphe (GPP pour \emph{Graph
%Partitioning Problem}) est le suivant : comment diviser les sommets
%d'un graphe en sous-ensembles de m\^eme cardinalit\'e (ou de m\^eme poids)
%tout en minimisant le nombre d'ar\^etes reliant des sommets appartenant
%\`a des sous-ensembles distincts (en d'autres termes, le poids de la
%coupe) ?
%
%{[}\'eventuellement SCHEMA reprenant fig.1 Chamberlain]
%
%Le probl\`eme du partitionnement est un probl\`eme NP-complet {[}M. R.
%Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete
%graph problems. Theoretical Computer Science, 1(3):237\textendash{}267,
%1976.], nous privant d'une solution optimale. Malgr\'e cette limitation
%th\'eorique, de nombreux algorithmes de partitionnement de graphe ont
%\'et\'e d\'evelopp\'es durant la derni\`ere d\'ecennie, approximant la solution
%optimale de mani\`ere satisfaisante et en un temps acceptable. 

Dans le cas standard du partitionnement de graphe, celui-ci ne change pas pendant le processus
: ni $S$, ni $A$ (ni les poids \'eventuels associ\'es au arcs) ne sont
modifi\'es. En cons\'equent, un partitionnement unique peut suffir (pour
un nombre de partitions fix\'e). En revanche dans le cas dynamique,
qui est le notre, le partitionnement peut n\'ecessiter plusieurs it\'erations.
On parle alors de probl\`eme de \textbf{repartitionnement de graphe}
@misc\{ fjallstrom98algorithms, author = \char`\"{}P. Fjallstrom\char`\"{},
title = \char`\"{}Algorithms for graph partitioning: A survey\char`\"{},
text = \char`\"{}Fjallstrom, P.-O. (1998). Algorithms for graph partitioning:
A survey. Linkoping Electronic Atricles in Computer and Information
Science, 3.\char`\"{}, year = \char`\"{}1998\char`\"{}, url = \char`\"{}citeseer.ist.psu.edu/358582.html\char`\"{}
\}. M\^eme si l'application d'algorithmes \og statiques \fg{} reste
une possibilit\'e, il est souvent plus avantageux d'employer alors des
algorithmes qui prennent en consid\'eration le partitionnement courant
pour tenter de l'am\'eliorer.

\paragraph{Formulation du probl\`eme dans PosNet}
La fonction de co\^ut que l'on associe au repartitionnement doit permettre \`a la fois : 
\begin{itemize}
\item De minimiser la longueur moyenne des routes dans l'overlay (rappel : la longueur d'une route est \'egale au nombre de sauts dans le r\'eseau effectu\'es durant 
toute la recherche) ;
\item De minimiser le nombre de noeuds s\'emantiques adjacents \`a une autre partition, autrement dit minimiser la taille des tables de routage. 
\end{itemize}
Ces deux objectifs sont contradictoires. Il s'agit donc de trouver un compromis entre les cas limites suivants : 

\begin{itemize}
\item Cas \og tout le monde connait tout le monde \fg{} : les pairs sont
connect\'es en clique et une requ\^ete peut \^etre achemin\'ee en un seul
saut, quelques soient les noeuds source et destination. En contrepartie,
le degr\'e est maximal 
\item Cas \og chacun connait un seul voisin \fg{} : le degr\'e est minimal
mais les routes s'allongent (en pire cas, longueur \'egale \`a $n$, avec
$n$ le nombre de noeuds dans le r\'eseau)
\end{itemize}


\paragraph{Solutions \`a l'\'etude}
Dans un r\'eseau social, le cluster correspond \`a un ensemble de personnes qui interagissent plus entre eux qu'avec le reste de la communaut\'e. Dans PosNet, chaque cluster 
serait un sous graphe du graphe s\'emantique dont les noeuds s\'emantiques sont fr\'equemment travers\'es par un m\^eme chemin sans vall\'ee. Le traitement du probl\`eme de 
partitionnement de graphe s\'emantique par le biais d'algorithmes de clusterisation, pourrait permettre d'obtenir un algorithme dont le temps de traitement est 
proportionnel au nombre de partitions ou clusters et non pas \`a la taille du graphe initial.


\begin{itemize}
\item Repartitionnement \`a chaque entr\'ee (resp. d\'epart) de noeud en $m$
partitions, avec $m$ le nombre de pairs total, \`a l'inclusion (resp.
exclusion) du pair arrivant (resp. partant), selon une approche multi-niveau
parall\`ele. Contraction selon CSV de centralit\'e maximale et partitionnement
selon ??? Probl\`eme : Implication de l'ensemble de pairs \`a chaque entr\'ee/d\'epart
=> Est il possible de limiter le repartitionnement au voisinage du
pair de rattachement ? 
\item Etudier : http://www.cs.ucsd.edu/\textasciitilde{}vahdat/papers/mascots03.pdf
{[}@misc\{ yocum03toward, author = \char`\"{}K. Yocum and E. Eade
and J. Degesys and D. Becker and J. Chase and A. Vahdat\char`\"{},
title = \char`\"{}Toward Scaling Network Emulation using Topology
Partitioning\char`\"{}, text = \char`\"{}K. Yocum, E. Eade, J. Degesys,
D. Becker, J. Chase, and A. Vahdat. Toward Scaling Network Emulation
using Topology Partitioning. In Proc. of MASCOTS 2003.\char`\"{},
year = \char`\"{}2003\char`\"{}, url = \char`\"{}citeseer.ist.psu.edu/yocum03toward.html\char`\"{}
\}]
\end{itemize}
{[}Partition initiale : peut \^etre al\'eatoire mais meilleure est la
partition initiale, plus rapide est l'obtention de la solution finale
{[}Walshaw et Cross \og Parallel Mesh Partitioning on Distributed
Memory Systems \fg{}] => r\'eutilisation par ex. de l'algo courant
qui partitionne le GS \og verticalement \fg{}]

{[}Variation par-rapport \`a KL : la mod\'elisation du \og gain \fg{}
(fonction objectif \`a maximiser dans KL : la valeur de la coupe). (Questions
subsidiaires : L'\'etape de raffinement peut elle s'effectuer it\'erativement
tout au long du cycle de vie du syst\`eme ? Pendant les p\'eriodes oisives
? Quel est le co\^ut de la mise-\`a-jour pour un pair ?)]

\section{Gestion de la concurrence}
En pratique, PosNet doit pouvoir g\'erer les requ\^etes d'ajout et de
retrait de ressources simultan\'ees, ainsi que les requ\^etes simultan\'ees
d'entr\'ee et de d\'epart de pairs. Cette section pr\'esente donc les modifications
\`a apporter aux algorithmes de la section pr\'ec\'edente, pour que soient
prises en compte les requ\^etes concurrentes. 

En plus des invariants pr\'esent\'es en \ref{sec:Cas-s=0000E9quentiel},
une contrainte suppl\'ementaire s'impose ici : la continuit\'e des services
de la couche requ\^ete. En effet, les recherches et les mises-\`a-jours
se d\'eroulant en parall\`ele dans l'overlay, on veut n\'eanmoins assurer
que les recherches ne soient pas interrompues durant les mise-\`a-jour. 

\subsection{Ajout et retrait d'une ressource}
Les requ\^etes concurrentes se partagent le graphe s\'emantique. Les requ\^etes
de recherche y acc\'edent en lecture seule ; les macro-modifications
en \'ecriture et en lecture. Toute op\'eration d'\'ecriture sur le graphe
s\'emantique doit \^etre consid\'er\'ee comme une section critique, n\'ecessitant
un protocole d'entr\'ee/sortie afin : 

\begin{itemize}
\item de n'en permettre l'acc\'`es qu'\`a un seul \'ecrivain \`a la fois, 
\item d'en permettre l'acc\`es \`a la fois \`a un \'ecrivain et \`a un nombre quelconque
de lecteurs. 
\end{itemize}

\subsubsection{Exclusion mutuelle des \'ecrivains}

L'algorithme s\'equentiel vu en \ref{sub:Ajout-et-retrait} d\'ecrit la
transformation du graphe s\'emantique r\'esultant de l'ajout ou du retrait
du noeud associ\'e \`a une ressource. Cette transformation s'effectue
en deux \'etapes : i) calcul des transformations et ii) r\'e\'ecriture {[}i)
calcul du sous graphe, ii) remplacement]. En cas d'acc\`es concurrent
par des macro-modifications, ces deux sections deviennent critiques
: les op\'erations de calcul et de r\'e\'ecriture n'\'etant pas atomiques,
l'\'etat du graphe peut \'evoluer entre le d\'ebut et la fin des op\'erations. 

Le protocole d'acc\`es \`a une section critique doit v\'erifier : i) l'exclusion
mutuelle : au plus une t\^ ache de contr\^ole ex\'ecute une section critique
donn\'ee ; ii) l'absence de deadlock : si deux ou plus de t\^ aches de
contr\^ole tentent d'acc\'eder \`a une section critique, l'une d'elles au
moins va y parvenir. (aussi : \'equit\'e, d\'elais raisonnable et justifi\'e...). 

Plusieurs types strat\'egies sont propos\'ees dans le domaine de la programmation
concurrente. Le choix d'une strat\'egie d\'epend des caract\'eristiques
du probl\`eme. Dans le cas sp\'ecifique de PosNet, interviennent les hypoth\`eses
suivantes : i) les \'ecritures sont largement plus nombreuses que les
lectures ; ii) une mise-\`a-jour est co\^uteuse (peut fait intervenir
d'autres pairs => co\^ut en termes de communications) ; iii) la taille
du sous-graphe modifi\'e est faible par-rapport \`a la taille totale du
graphe. Ce que l'on peut traduire par les crit\`eres de choix de strat\'egie
suivants : i) optimisme : on \'evite les conflits avec les lectures,
m\^eme en contrepartie d'un co\^ut \'elev\'e de r\'esolution de conflit avec
une \'ecriture ; ii) anticipation : on pr\'ef\`ere une approche \og pr\'eventive \fg{}
(anticipation/pr\'evention des conflits) \`a une approche curative (n\'ecessitant
de \og d\'etricoter \fg{} une s\'equence de modifications en cas de
conflit : \emph{roll}-\emph{back} \emph{transaction}) ; iii) optimisation.
Ces caract\'eristiques g\'en\'erales de PosNet se doublent de caract\'eristiques
propres \`a chaque section critique : lors du calcul du sous-graphe
`a modifier, les noeuds \`a v\'erouiller ne sont pas connus (puisqu'ils
sont d\'etermin\'es dans cette section). A contrario, ils sont connus
lorsque l'on rentre dans la section critique du remplacement. 

La mise en oeuvre classique des sections critiques consiste en l'utilisation
de cadenas/verrous. Approches alternatives : 

\begin{itemize}
\item \emph{wait free, lock}-\emph{free} : mais approche complexe, r\'eserv\'ee
\`a des structures de donn\'ees simples car n\'ecessite de la part du mat\'eriel
des primitives atomiques (type \emph{\og compare and swap} \fg{}).
En effet, une impl\'ementation lock-free de l'ajout/la suppression d'une
ressource consisterait \`a effectuer les op\'erations de modifications
sur une copie locale du sous-graphe, puis de tester si celui-ci a
\'et\'e modifi\'e entretemps. Si non : on remplace l'ancien sous-graphe
par la copie modifi\'ee. Si oui : on recalcule le nouveau sous-graphe
et on recommence (copie, modifications, tests). Probl\`eme : les op\'erations
de test et de remplacement ne sont pas atomiques... 
\item \emph{\og lazy \fg{}} : mais approche curative 
\end{itemize}
On consid\`ere donc une approche \emph{lock}-\emph{based}/l'utilisation
de verrous. Une strat\'egie possible est le verrouillage int\'egral en
\'ecriture des noeuds des sous-graphes de chaque pair durant toute la
dur\'ee des deux sections critiques. Ce proc\'ed\'e a le m\'erite de la simplicit\'e,
en ramenant le cas concurrent au cas s\'equentiel (on s\'equentialise
les requ\^etes en les contenant). N\'eanmoins, il provoque une contention
maximale des macro-modifications. 

D'o\`u les optimisations en cours d'\'evaluation : 

\begin{enumerate}
\item Strat\'egie \og optimiste \fg{} : 

\begin{enumerate}
\item Calcul du sous-graphe : lock-free. Pour chaque noeud appartenant au
sous-graphe, l'\'etat courant est enregistr\'e
\item Remplacement : v\'erouillage local limit\'e au sous-graphe. avant d'entreprendre
les modifications, on compare l'\'etat courant de chaque noeud avec
l'\'etat enregistr\'e. Si aucun noeud n'a subi de modification (\'egalit\'e
pour chaque noeud), alors les modifications sont entreprises. Dans
le cas contraire (au moins un noeud poss\`ede un \'etat courant diff\'erent
de l'\'etat enregistr\'e), alors retour \`a l'\'etape (a). 
\end{enumerate}
\item Strat\'egie \og prudente \fg{} : 

\begin{enumerate}
\item Calcul du sous-graphe : v\'erouillage en \'ecriture de la totalit\'e du
graphe s\'emantique. Permet le d\'eroulement simultan\'e de t\^ aches de recherche
et de t\^ aches de calcul de sous-graphe, mais interdit le d\'eroulement
simultan\'e d'une t\^ ache de calcul et d'une t\^ ache de remplacement. Probl\`eme
: introduit un \'el\'ement de centralit\'e dans le syst\`eme (tous les pairs
sont impliqu\'es). Une fois d\'etermin\'e le sous-graphe \`a modifier, le
reste du graphe est \og rel\^ach\'e \fg{}. 
\item Remplacement : v\'erouillage local limit\'e au sous-graphe \`a modifier.
Pour \'eviter les probl\`emes d'interblocage, la possibilit\'e d'introduire
un ordre sur les verrous est \`a l'\'etude. 
\end{enumerate}
\end{enumerate}

\subsubsection{Cohabitation d'un \'ecrivain et de $n$ lecteurs}

Afin d'\'eviter la contention en lecture {[}contention des acc\`es en
lecture] pendant une \'ecriture, le \emph{control} \emph{plane} exploite
la transitivit\'e de la relation d'ordre. Le principe est le suivant
: lors d'une modification du graphe, les anciens noeuds et relations
ne sont supprim\'es qu'une fois les nouveaux noeuds et relations mis
en place. Une requ\^ete de recherche peut ainsi traverser des graphes
en cours de mise-\`a-jour sans perturber celle-ci ni encourir de d\'elai
suppl\'ementaire. 


\subsection{Entr\'ee et d\'epart d'un pair}

Section critique : v\'erouillage du pair de rattachement et de ses voisins. 

\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_

{[}REFS/FORMALISME/COMPARAISON : http://staffweb.cms.gre.ac.uk/\textasciitilde{}wc06/partition/]

{[}VULGARISATION : http://www.cs.washington.edu/homes/brad/cv/pubs/degree/generals.pdf]

Approche g\'eom\'etrique distribu\'e du partitionnement

Dans ce contexte, les solutions g\'eom\'etriques peuvent appara\^itre avantageuses.
Leur principe repose sur la repr\'esentation des noeuds de $G$ dans
un espace vectoriel et l'utilisation de leurs coordonn\'ees g\'eom\'etriques
pour les partitionner selon des hyperplans {[}citer Recursive Coordinate
Bisection, Recursive Inertial Bisection, Unbalanced Recursive Bisection,
circle based bisection, REFS dans Walshaw et Cross \og Parallel Mesh
Partitioning on Distributed Memory Systems \fg{} + Chamberlain].
Les diverses strat\'egies misent en oeuvre ne n\'ecessitent que d'appliquer
de mani\`ere it\'erative des algorithmes parall\`eles de tri. Elles sont
donc tr\`es rapides et faciles \`a impl\'ementer {[}Walshaw et Cross \og Parallel
Mesh Partitioning on Distributed Memory Systems \fg{}].\underbar{
}N\'eanmoins, elle p\^atissent de nombreuses limitations qui en excluent
l'application \`a PosNet : hypoth\`eses sur la distribution des noeuds
(exigence d'une forte corr\'elation entre proximit\'e spatiale et voisinage)
=> d\'egradation de la solution en cas de distribution de donn\'ees non
uniforme ; partitionnement selon hyperplans simpliste ; solutions
moins bonnes que par des approches orient\'ees graphe. 

%\section{Annexe}
%\paragraph{Bref survol du domaine des solutions standards en th\'eorie des graphes}
%
%Les solutions propos\'ees sont suppos\'es r\'epondrent \`a deux pr\'eoccupations
%principales lors de la distribution des applications : i) la r\'epartition
%de la charge entre processeurs ; ii) la minimisation des co\^uts induits
%par la distribution des traitement, principalement en terme de co\^uts
%de communication entre pairs.
%
%Malheureusement, ces solutions ne peuvent \^etre appliqu\'ees telles qu'elles
%\`a notre probl\'ematique. En effet, au regard de notre probl\'ematique,
% le GPP n'optimise donc pas les \og bonnes \fg{} m\'etriques : 
%
%\begin{itemize}
%\item \underbar{Mod\`ele de co\^ut de la communication :} Hendrickson dans {[}B.
%Hendrickson and T. G. Kolda. Graph Partitioning Models for Parallel
%Computing. Parallel Comput., 26(12):1519-1534, 2000, \og Graph Partitioning
%and Parallel Solvers: Has the Emperor No Clothes ? \fg{}] d\'esigne
%en tant que principale limitation de la mod\'elisation par GPP le fait
%que la m\'etrique minimis\'ee (taille ou valeur de la coupe) ne refl\^ete
%par directement le co\^ut de la communication dans l'application mod\'elis\'ee.
%L'une des raisons \`a cela est simplement la difficult\'e \`a mod\'eliser
%ce co\^ut (et la facilit\'e \`a minimiser une coupe !). Dans PosNet, \`a un
%lien logique entre deux pairs correspond 1..n liens dans le GS =>
%minimiser la taille de la coupe dans le GS ne minimise pas forc\'ement
%la coupe dans l'overlay. Qui plus est, la taille de la coupe n'est
%pas n\'ecessairement en rapport avec le volume des communications\textbf{. }
%\item \underbar{R\'epartition de la charge :} Dans l'hypoth\`ese o\`u les pairs
%sont homog\`enes%
%\footnote{Pairs sont homog\`enes = de capacit\'e \'egale. La gestion de l'h\'et\'erog\'en\'eit\'e
%des pairs n'est pas adress\'ee ici.%
%}, on cherche \`a r\'epartir \'egalement les traitements. Si chaque noeud
%correspond une op\'eration de calcul (comparaison), c'est \`a un CSV que
%correspond le traitement d'une requ\^ete. Un \og bon \fg{} partitionnement
%dans notre cas doit donc s'assurer que les pairs se voient assign\'es
%une portion \'egale des routes emprunt\'ees sur le total des routes possibles.
%Or les noeuds ne sont pas \'egaux entre eux au regard de la politique
%de routage, ie les noeuds du GS n'ont pas m\^eme \og centralit\'e \fg{}
%(cf. noeud maximaux par ex.) => Il ne suffit pas de r\'epartir \'equitablement
%les noeuds s\'emantiques entre les pairs pour parvenir r\'epartir la charge.
%Il faut r\'epartir les noeuds en fonction de leur centralit\'e {[}mais
%est ce possible ?]. 
%\end{itemize}
%La question se pose alors de savoir si en adaptant les heuristiques,
%on peut tout de m\^eme se ramener \`a notre probl\`eme. Par ex., en re-d\'efinissant
%un nouveau gain dans l'heuristique de Kernighan-Lin, qui ne soit ni
%la r\'epartition \'equitable des noeuds ni le poids de la coupe. 
%
%Pr\'esentation de deux heuristiques classiques qui pourraient \^etre adapt\'ees
%:
%
%
%\subparagraph{Approche par raffinement (Kernighan-Lin ou KL)}
%
%La plus ancienne (1970). Principe de la descente de gradient (\emph{random-restart
%hill climbing}). En deux temps : i) partitionnement initial, puis
%ii) migration de noeuds s\'emantiques en minimisant une fonction objectif.
%On suppose qu'il est possible d'associer un \og gain \fg{} \`a chaque
%sommet de \og bordure \fg{} $u$ d'une partition $S_{p}$ reli\'e
%\`a un sommet $v$ d'une partition $S_{q}$, correspondant au b\'en\'efice
%de la migration de $u$ dans $S_{q}$ pour le processeur $p$. Une
%impl\'ementation typique de l'algorithme de raffinement KL comporte
%deux boucles imbriqu\'ees. Grossi\`erement, \`a chaque \og passe \fg{}
%la boucle \og interne \fg{} s\'electionne un sommet (en g\'en\'eral celui
%dont le gain associ\'e est le plus \'elev\'e) et ex\'ecute la migration (sans
%oublier de mettre-\`a-jour les gains qui en seraient modifi\'es), puis
%r\'ep\'ete ce processus jusqu'\`a avoir visit\'e tous les sommets de bordure.
%La boucle \og externe \fg{} it\`ere la boucle interne jusqu'\`a parvenir
%un optimum (local).
%
%{[}SCHEMA avec graphes, partitions, poids]
%
%Dose d'al\'eatoire utilis\'ee pour \'eviter les maximaux locaux, en enregistrant
%la meilleure partition \`a chaque \'etape de raffinement. 
%
%Variation classique propos\'ee par Fiduccia et Mattheyses et d\'esign\'ee
%sous le nom de KL/FM, permettant de ramener la complexit\'e de KL ($O(n^{2})$)
%\`a $O(n)$ (avec $n$ le nombre de sommets) grace \`a l'utilisation de
%structure de donn\'ees appropri\'ees. {[}A COMPLETER]
%
%\underbar{Avantages g\'en\'eraux de l'approche :} \emph{\og Random-restart
%hill climbing is a surprisingly effective algorithm in many cases.
%It turns out that it is often better to spend CPU time exploring the
%space, rather than carefully optimizing from an initial condition \fg{}}.
%\underbar{Limitations g\'en\'erales de l'approche :} Cette m\'ethode ne
%fonctionne bien que si l'on a une fonction heuristique tr\'es instructive
%{[}ou si le syst\`eme de transition est commutatif .......... huh ?]
%
%
%\subparagraph{Approches multi-niveaux (\emph{multilevel techniques})}
%
%Propos\'ee par Barnard et Simon {[}REF] et \'etendue par Hendrickson et
%Leland, puis par Bui et Jones. En trois phases {[}cf. aussi explications
%dans Karypis et Kumar \og A Coarse-Grain Parallel Formulation of
%Multilevel $k$-way Graph Partitioning Algorithm \fg{}]. Fait appel
%\`a KL : 
%
%\begin{enumerate}
%\item Contraction : Contraction du graphe d'origine $G$, en groupant (\emph{matching})
%les sommets pour former des clusters ou super-noeuds. Ces super-noeuds
%d\'efinissent un nouveau graphe \og gros grains \fg{} poss\'edant un
%nombre de sommets moindre. It\'erer la proc\'edure de contraction jusqu'\`a
%parvenir \`a un graphe $G_{m}$ suffisamment contract\'e pour permettre
%le calcul d'une solution de partitionnement optimale $S_{m}$. Algorithmes
%de Matching, Maximal Matching : Random Matching (RM), Heavy Edge Matching
%(HEM), Light Edge Matching (LEM), Heavy Clique Matching (HCM) ;
%\item Partitionnement : Calcul de k partitions de haute qualit\'e (ie de coupe
%minimale), avec des partitions de tailles \'equivalentes (grosso modo
%$|N|/k$). Algorithmes : Spectral Bisection (SB), KL/FM, Graph Growing
%Algorithm (GGP), Greedy Graph Growing Algorithm (GGGP) ; 
%\item Inflation : Interpolation et raffinement par KL de $S_{m}$sur chacune
%des solutions prises dans l'ordre de la taille croissante en commen\c cant
%par $G_{m}$, jusqu'\`a obtention d'une solution pour $G$. 
%\end{enumerate}
%{[}SCHEMA en V, Karypis et Kumar \og A Coarse-Grain Parallel Formulation
%of Multilevel $k$-way Graph Partitioning Algorithm \fg{}]
%
%D\'etails contraction\emph{ }: 
%
%\begin{itemize}
%\item \emph{Maximal Matching} de Hendrickson et Leland. On appelle \emph{matching
%}d'un graphe $G(N,E)$ un sous-ensemble $E_{m}$de $E$ tel qu'aucune
%paire d'ar\^etes dans $E_{m}$ ne partagent d'extr\'emit\'e. Un \emph{maximal
%matching} de $G$ est un \emph{matching $E_{m}$ }tel qu'aucune ar\^ete
%ne peut lui \^etre ajout\'ee et que $E_{m}$demeure un \emph{matching}.
%Calculable en $O(E)$ par un algorithme glouton. 
%
%
%{[}SCHEMA matching maximal]
%
%\item Autres heuristiques pour la contraction {[}pas comprises !] : Hogstedt
%et al. {[}\og Graph Cutting Algorithms for Distributed Applications
%Partitioning \fg{}]. Les transformations propos\'ees pr\'eservant la
%structure de $G$ (chaque noeud de $G$ correspond \`a un unique multinoeud
%dans $G_{m}$ + coupe et poids des sous-graphes identiques \`a leurs
%contreparties dans $G$ => \og \emph{optimally} \emph{preserving} \fg{}
%?), la solution pour $G$ se d\'eduit directement de la solution pour
%$G_{m}$.\underbar{ }
%\end{itemize}
%{[}SCHEMA de contraction de graphe, id. ou Chamberlain]
%
%\underbar{Avantages :} Contraction peu co\^uteuse ; approche multi-niveaux
%plus rapide que l'approche \og en bloc \fg{} (mono-niveau) ; solution
%tr\`es satisfaisante, voire in\'egal\'ee @misc\{ fjallstrom98algorithms,
%author = \char`\"{}P. Fjallstrom\char`\"{}, title = \char`\"{}Algorithms
%for graph partitioning: A survey\char`\"{}, text = \char`\"{}Fjallstrom,
%P.-O. (1998). Algorithms for graph partitioning: A survey. Linkoping
%Electronic Atricles in Computer and Information Science, 3.\char`\"{},
%year = \char`\"{}1998\char`\"{}, url = \char`\"{}citeseer.ist.psu.edu/358582.html\char`\"{}
%\}\\
%
%
%La limitation commune de ces deux heuristiques est de reposer sur
%des connaissances globales sur le graphe pour le partitionner. Leur
%distribution est difficile {[}Chamberlain]. 
%
%
%\paragraph{Distribution du partitionnement}
%
%{[}Pour les REFS : Karypis et Kumar \og A Coarse-Grain Parallel Formulation
%of Multilevel $k$-way Graph Partitioning Algorithm \fg{}]
%
%La probl\'ematique commune \`a tous les algorithmes de partitionnement
%parall\`ele est la communication induite par l'acc\`es \`a un sommet situ\'e
%sur un pair voisin. En reprenant les algorithmes d\'ecrits pr\'ec\'edemment
%: 
%
%\begin{itemize}
%\item Parall\'elisation de l'approche par raffinement (heuristiques KL) :
%Le principal obstacle \`a la parall\'elisation d'un tel processus r\'eside
%dans la boucle interne. La migration s\'equentiel des noeuds implique
%un surco\^ut important en termes de communications {[}Walshaw et Cross
%\og Parallel Mesh Partitioning on Distributed Memory Systems \fg{}]
%=> impl\'ementation moins \og naive \fg{} : migration \og en bloc \fg{}
%de noeuds (\emph{bulk migration scheme}). Un autre obstacle r\'eside
%dans le choix des sommets \`a migrer. Le processus de d\'ecision est en
%effet sujet \`a collision. En reprenant l'ex. ci-dessus : les processeurs
%$p$ et $q$ d\'ecident simultan\'ement de migrer (resp.) $u$ vers $S_{q}$
%et $v$ vers $S_{p}$. Une solution propos\'ee par {[}Diniz \emph{et
%al.}] : n'autoriser l'\'echange de noeuds qu'entre pairs voisins (?).
%Mais solutions peu satisfaisantes par-rapport \`a une application centralis\'ee
%(permettant l'\'echange de noeuds dans partitions arbitraires). {[}Walshaw
%and Cross \og Parallel Optimisation Algorithms for Multilevel Mesh
%Partitioning \fg{}] pr\'esentent trois diff\'erents algorithmes pour
%choisir en parall\`ele les sommets \`a migrer, de telle sorte \`a \'eviter
%les collisions. Toutefois, {[}Karypis et Kumar \og A Coarse-Grain
%Parallel Formulation of Multilevel $k$-way Graph Partitioning Algorithm \fg{}]
%font \'etat du caract\`ere fondamentalement s\'equentiel de KL et souligne
%que les tentatives de parall\'elisation se sont sold\'ees par des r\'esultats
%mitig\'es {[}REFS id.]. Les auteurs de \og Parallel Mesh Partitioning
%on Distributed Memory Systems \fg{} les rejoignent en accordant que
%{[}eux-m\^eme qu'\'etant donn\'e le caract\`ere intrins\`equement \og local \fg{}
%des optimisations men\'ees par KL,] l'approche multi-niveaux est reconnue
%plus efficace que celle par raffinement. 
%\item Parall\'elisation de l'approche multi-niveaux (techniques de contraction/optimisation).
%La principale difficult\'e \`a parall\'eliser les algorithmes de partitionnement
%multi-niveaux provient notamment de l'\'etape de contraction, laquelle
%implique de \og fusionner \fg{} des sommets adjacents. A partir
%d'un partitionnement initial al\'eatoire, cette \'etape peut requ\'erir
%beaucoup de communications {[}REFS dans Karypis et Kumar \og A Coarse-Grain
%Parallel Formulation of Multilevel $k$-way Graph Partitioning Algorithm \fg{}
%p.2]. 
%
%\begin{itemize}
%\item {[}Walshaw et Cross \og Parallel Mesh Partitioning on Distributed
%Memory Systems \fg{}] : Propose une variante de l'algorithme de contraction
%de Hendrickson et Laland (lui m\^eme bas\'e sur l'algorithme de calcul
%parall\`ele du \emph{maximal matching }de Luby ?). 
%\item {[}Walshaw, Cross \og Parallel optimisation algorithms for multilevel
%mesh partitioning \fg{}] : Trois algorithmes parall\`eles pour le raffinement
%et si n\'ecessaire la r\'epartition de charge. 
%\item PMRSB {[}Barnard] 
%\item ParMETIS {[}Karypis et Kumar \og A Coarse-Grain Parallel Formulation
%of Multilevel $k$-way Graph Partitioning Algorithm \fg{}] : Colorisation
%du graphe (sommets adjacents de couleur diff\'erentes => maximal matching
%calcul\'e en it\'erant sur les couleurs)
%\end{itemize}
%\end{itemize}
%Note : Quelque soit la qualit\'e de la solution de partitionnement \`a
%laquelle on puisse aboutir, il y a toujours un b\'en\'efice \`a appliquer
%en post-traitement un raffinement local en utilisant KL/FM ou une
%de ses variantes (du \`a la complexit\'e du probl\`eme) {[}REF ?]. 
%
%{[}RELIRE \textbf{3.1 }@misc\{ fjallstrom98algorithms, author = \char`\"{}P.
%Fjallstrom\char`\"{}, title = \char`\"{}Algorithms for graph partitioning:
%A survey\char`\"{}, text = \char`\"{}Fjallstrom, P.-O. (1998). Algorithms
%for graph partitioning: A survey. Linkoping Electronic Atricles in
%Computer and Information Science, 3.\char`\"{}, year = \char`\"{}1998\char`\"{},
%url = \char`\"{}citeseer.ist.psu.edu/358582.html\char`\"{} \}]
